package mashibing.class16;

import java.util.*;

// OJ链接：https://www.lintcode.com/problem/topological-sorting
public class Class16_3_2_TopologicalOrderDFS2 {

    // 不要提交这个类
    public static class DirectedGraphNode {
        public int label;
        public ArrayList<DirectedGraphNode> neighbors;

        public DirectedGraphNode(int x) {
            label = x;
            neighbors = new ArrayList<DirectedGraphNode>();
        }
    }

    // 提交下面的
    public static class Record {
        public DirectedGraphNode node;
        public long nodes;

        public Record(DirectedGraphNode n, long o) {
            node = n;
            nodes = o;
        }
    }

    /**
     * @param graph: A list of Directed graph node
     * @return: Any topological order for the given graph.
     */
    public static ArrayList<DirectedGraphNode> topSort(ArrayList<DirectedGraphNode> graph) {
        // write your code here
        Map<DirectedGraphNode, Record> order = new HashMap<>();
        for (DirectedGraphNode node : graph) {
            f(node, order);
        }
        List<Record> list = new ArrayList<>(order.values());
        list.sort(new Comparator<Record>(){
            @Override
            public int compare(Record o1, Record o2) {
                return Long.compare(o2.nodes, o1.nodes);
            }
        });
        ArrayList<DirectedGraphNode> res = new ArrayList<>();
        for (Record record : list) {
            res.add(record.node);
        }
        return res;
    }

    public static Record f(DirectedGraphNode cur, Map<DirectedGraphNode, Record> order) {
        if (order.containsKey(cur)) {
            return order.get(cur);
        }
        long count = 0;
        for (DirectedGraphNode neighbor : cur.neighbors) {
            count += f(neighbor, order).nodes;
        }
        Record record = new Record(cur, count + 1);
        order.put(cur, record);
        return record;
    }
}
